SRM 702

Match Summary

Round Overview
Discuss this match

TestTaking

To maximize our number of points, we maximize the number of true answers that are correct and false answers that are correct. The number of true answers that are correct is at most min(guessed, actual). Symmetrically, the max number of false answers that are correct is min(questions-guessed, questions-actual).

Another way of looking at it is to minimize the number of responses that are different. There are a minimum of abs(guessed-actual) responses that can be different, so the answer can also be computed as questions-abs(guessed-actual)

Python

1
2
3
class TestTaking:
  def findMax(self, questions, guessed, actual):
  return min(guessed, actual) + min(questions - guessed, questions - actual)

GridSort

we can try sorting the columns in increasing order by first row, and then sort the rows in increasing order by the first column, then check that this is valid solution. Alternatively, we can check that every value in a row has the same value when divided by m and floored, and every value in a column has the same value modulo m.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.HashSet;

public class GridSort {
  public String sort(int n, int m, int[] grid) {
    for (int i = 0; i < n; i++) {
      HashSet < integer > hs = new HashSet();
      for (int j = 0; j < m; j++) {
        hs.add((grid[i * m + j] - 1) / m);
      }
      if (hs.size() != 1) return "Impossible";
    }
    for (int j = 0; j < m; j++) {
      HashSet < integer > hs = new HashSet();
      for (int i = 0; i < n; i++) {
        hs.add((grid[i * m + j] - 1) % m);
      }
      if (hs.size() != 1) return "Impossible";
    }
    return "Possible";
  }
}

SubsetSumExtreme

This is a classic bitmask dp problem. For each face, we can compute the masks that can reach it. Then, given a mask, we can iterate through all faces that can come up, and choose the best mask.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.Arrays;
import java.util.HashSet;

public class SubsetSumExtreme {
  public double getExpectation(int[] row, int[] dice) {
    int n = row.length, m = dice.length;
    int[] sum = new int[1 << n];
    hashset < integer = "" > [] masks = new HashSet[1001 * n];
    for (int i = 0; i < masks.length; i++) masks[i] = new HashSet < > ();
    for (int i = 1; i < 1 << n; i++) {
      int w = Integer.numberOfTrailingZeros(i & -i);
      sum[i] = sum[i ^ (1 << w)] += ""
      row[w]; = ""
      masks[sum[i]].add(i); = ""
    } = ""
    double[] = ""
    exp = "new"
    double[1 = "" <<= ""
      n]; = ""
    for = ""(int = ""
      left = "0;" <= ""
      1 = ""
      n; = ""
      left++) = "" {
      = ""
      double = ""
      def = "sum[left];"
      choices = "new"
      double[m]; = ""
      arrays.fill(choices, = ""
        def); = ""
      submask = "left;" > 0;
      submask = (submask - 1) & left) {
      for (int i = 0; i < m; i++) {
        if (masks[dice[i]].contains(submask)) {
          choices[i] = Math.min(choices[i], exp[left ^ submask]);
        }
      }
    }
    for (int i = 0; i < m; i++) {
      exp[left] += choices[i] / (double) m;
    }
  }
  return exp[(1 << n) - 1];
} = "" <= ""
pre = "" >
  <
  /n)-1];></w)] > < /n];>

GridSortMax

Greedily put 1 in the correct position, then 2, then 3, and so on. Once we put a number in a position, it’s row/column are locked and can’t be used in future swaps.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class GridSortMax {
  public String findMax(int n, int m, int[] grid) {
    int[] col = new int[n * m];
    int[] row = new int[n * m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        row[grid[i * m + j] - 1] = i;
        col[grid[i * m + j] - 1] = j;
      }
    }

    boolean[] lockedr = new boolean[n];
    boolean[] lockedc = new boolean[m];
    int[] pr = new int[n];
    int[] pc = new int[m];
    int[] ir = new int[n];
    int[] ic = new int[m];
    for (int i = 0; i < n; i++) pr[i] = ir[i] = i;
    for (int i = 0; i < m; i++) pc[i] = ic[i] = i;

    char[] ret = new char[n * m];
    for (int i = 0; i < n * m; i++) {
      int needr = i / m, needc = i % m;
      fix(pr, ir, lockedr, row[i], needr);
      fix(pc, ic, lockedc, col[i], needc);
      if (pr[row[i]] == needr && pc[col[i]] == needc) {
        lockedr[needr] = true;
        lockedc[needc] = true;
        ret[i] = '1';
      } else {
        ret[i] = '0';
      }
    }
    return new String(ret);
  }

  public static void fix(int[] perm, int[] inv, boolean[] locked, int cur, int need) {
    if (perm[cur] != need) {
      if (!locked[perm[cur]] && !locked[need]) {
        int ww = inv[need];
        int t = inv[perm[cur]];
        inv[perm[cur]] = ww;
        inv[need] = t;

        t = perm[cur];
        perm[cur] = need;
        perm[ww] = t;
      }
    }
  }
}

RepeatedStrings

Write the following dp: dp[i] = sum_k where k divides (i-2) dp[k] The number of good strings of length at most 150 is sum dp[i] for i from 0 to 150. You can check this value is pretty small, so just generate all good strings, sort them, and check that it is a subsequence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.ArrayList;
import java.util.Collections;

public class RepeatedStrings {
  public String findKth(String s, int k) {
    ArrayList < string > interesting = new ArrayList();
    interesting.add("()");
    for (int len = 4; len <= s.length(); len += 2) {
      for (int i = 0; i < interesting.size(); i++) {
        String gg = interesting.get(i);
        if ((len - 2) % gg.length() == 0) {
          String nxt = "(" + new String(new char[(len - 2) / gg.length()])
            .replace("\0", gg) + ")";
          interesting.add(nxt);
        }
      }
    }
    Collections.sort(interesting);
    for (String mm: interesting) {
      int idx = 0;
      for (int i = 0; idx < mm.length() && i < s.length(); i++) {
        if (mm.charAt(idx) == s.charAt(i)) {
          idx++;
        }
      }
      if (idx == mm.length()) {
        if (--k == 0) return mm;
      }
    }
    return "";
  }
}

</string>

FindingFriends

First, let’s binary search for answer. So problem reduces to finding if there exists a happy sublist with length at least m and value k. For each number, we can compute the closest index on the left that has absolute value at most k, and the closest index on the right that has absolute value at most k. For example, if the list is equal to [8,1,10,2,9,7], and k=2, then left = [-1,-1,0,1,2,4], and right = [2,3,4,6,5,6]. This is a pretty standard problem and can be solved using some binary indexed trees and takes O(n log n) time. Now, consider the following pseudocode to check if all sublists are not happy:

1
2
3
4
5
6
7
8
9
def all_bad(s, e):
  if e - s <= m: # all subarrays are too short, so they are all bad
return true
find an index i such that left[i] < s and right[i] > e
if no index exists: # all numbers are not lonely
if we take the entire subarray
return false
# any subarray that contains index i will be bad, so we just need to check the two cases below.
return all_bad(s, i - 1) and all_bad(i + 1, e)

This is correct, but it is too slow. In particular, the line for finding the index is too slow if we try the straightforward loop from s to e. Instead, let’s just scan from both ends simultaneously. This now becomes O(n log n) (basic idea is the recurrence is now T(n) = T(a) + T(b) + min(a,b)). Overall time complexity is O(n log^2 n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <unordered_map>

#include <algorithm>

#include <iostream>

#include <iomanip>

#include <cstring>

#include <string>

#include <vector>

#include <cmath>

#include <map>

using namespace std;

#define MAXN 100001

struct BIT {
  int n;
  int s[MAXN];
  BIT(int _n) {
    n = _n;
    memset(s, 0, sizeof(s));
  }
  int lowbit(int x) {
    return x & (-x);
  }
  void add(int index, int value) {
    while (index <= n) {
      s[index] += value;
      index += lowbit(index);
    }
  }
  int lastNonZero(int index) {
    if (index == 0) return 0;
    while (index > 0 && s[index] == 0)
      index -= lowbit(index);
    if (index == 0) return 0;
    int R = index;
    int total = s[index];
    int len = lowbit(index);

    while (len != 1) {
      if (s[R - (len / 2)] != total) {
        total -= s[R - (len / 2)];
        len /= 2;
      } else {
        total = s[R - (len / 2)];
        R -= (len / 2);
        len /= 2;
      }
    }
    return R;
  }
};

int n;
int arr[100001];
int maxDiff;
int L[100001];
int R[100001];
int requireMinimalLength;

struct data {
  int index;
  int value;
  bool operator < (const data & that) const {
    return value < that.value;
  }
};

vector < data > dataList;
BIT * tree;

void solveL() {
  dataList.clear();
  for (int i = 1; i <= n; i++) {
    data t;
    t.index = i;
    t.value = arr[i];
    dataList.push_back(t);
  }
  sort(dataList.begin(), dataList.end());
  int lef = 0, rig = -1;
  tree = new BIT(n);
  for (int i = 0; i < n; i++) {
    while (rig + 1 < n && dataList[rig + 1].value <= dataList[i].value + maxDiff) {
      tree - > add(dataList[rig + 1].index, 1);
      rig++;
    }
    while (lef < n && dataList[lef].value < dataList[i].value - maxDiff) {
      tree - > add(dataList[lef].index, -1);
      lef++;
    }
    L[dataList[i].index] = tree - > lastNonZero(dataList[i].index - 1);
  }
}

void reverse() {
  for (int i = 1; i <= n / 2; i++) {
    swap(arr[i], arr[n + 1 - i]);
  }
}

void solveLAndR() {
  reverse();
  solveL();
  for (int i = 1; i <= n; i++) {
    R[i] = n + 1 - L[n + 1 - i];
  }
  reverse();
  solveL();
}

bool check(int lef, int rig) {
  if (rig - lef + 1 < requireMinimalLength) return false;
  int bad = -1;
  for (int d = 0;; d++) {
    if (lef + d > rig - d) break;

    if (L[lef + d] < lef && R[lef + d] > rig) {
      bad = lef + d;
      break;
    }
    if (L[rig - d] < lef && R[rig - d] > rig) {
      bad = rig - d;
      break;
    }
  }
  if (bad == -1) {
    return true;
  }
  if (check(lef, bad - 1)) return true;
  if (check(bad + 1, rig)) return true;
  return false;
}

bool exist(int _maxDiff) {
  maxDiff = _maxDiff;
  solveLAndR();
  return check(1, n);
}

int solve() {
  int lef = -1, rig = 1000000000, mid;
  while (rig - lef > 1) {
    mid = (lef + rig) / 2;
    if (exist(mid))
      rig = mid;
    else
      lef = mid;
  }
  return rig;
}

class FindingFriends {
  public: int shortestDistance(int len, vector < int > init, int a, int b, int c, int d, int m) {
    requireMinimalLength = m;
    n = len;
    for (int i = 1; i <= init.size(); i++) {
      arr[i] = init[i - 1];
    }
    for (int i = init.size() + 1; i <= n; i++) {
      arr[i] = (1 LL * arr[i - 1] * a + 1 LL * b * (i - 1) + c) % d;
    }
    return solve();
  }
};

</int> < /data></map > </cmath> < /vector></string > </cstring> < /iomanip></iostream > </algorithm> < /unordered_map>